//package work.rightAnswer;
//
//import java.util.ArrayList;
//import java.util.List;
//import java.util.Stack;
//
//class Solutio {
//    List<String> list = new ArrayList<>();
//    StringBuilder path = new StringBuilder();
//    public List<String> generateParenthesis(int n) {
//        char[] arr = new char[]{'(',')'};
//        backtracing(arr,n);
//        return list;
//    }
//
//    private void backtracing(char[] arr, int n) {
//        if(path.length()==2*n){
//            if(isVaild(path,n)){
//                list.add(new String(path));
//            }
//            return;
//        }
//
//        for (int i = 0; i < arr.length; i++) {
//            path.append(arr[i]);
//            backtracing(arr,n);
//            path.deleteCharAt(path.length()-1);
//        }
//    }
//
//    private boolean isVaild(StringBuilder path, int n) {
//        Stack<Character> stack = new Stack<>();
//        int count = 0;
//        for (int i = 0; i < path.length(); i++) {
//            char c = path.charAt(i);
//            if(c==')'){
//                if(stack.isEmpty()||stack.peek()==')'){
//                    return false;
//                }
//                stack.pop();
//                count++;
//                continue;
//            }
//            stack.push(c);
//        }
//
//        return count==n?true:false;
//    }
//}